{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python_defaultSpec_1598156549519",
   "display_name": "Python 3.8.3 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定范围 `[m, n]`，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。\n",
    "\n",
    "示例 1: \n",
    "```\n",
    "输入: [5,7]\n",
    "输出: 4\n",
    "```\n",
    "示例 2:\n",
    "```\n",
    "输入: [0,1]\n",
    "输出: 0\n",
    "```\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 思路\n",
    "\n",
    "看了下题解发现,直接要暴力是要超时的\n",
    "\n",
    "通过把10进制转成2进制，发现，每一位的变化是有规律的\n",
    "\n",
    "最小的一位， 1转0，或者0转1\n",
    "\n",
    "`0`, `1`, `10`, `11`, `100`, `101`, `110`, `111`, `1000`\n",
    "\n",
    "可以看出规律：每${2}^{0}$的时候，最后一位都会变化\n",
    "\n",
    "如果最后的结果是在${2}^{i}$次方的时候小于m了，那么结果就是把前一个数转成二进制，把i位后面的全部变成0,然后转成十进制"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "import q\n",
    "class Solution1:\n",
    "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        def to_dec(num, i):\n",
    "            print(num ,i)\n",
    "            x = format(num, 'b')\n",
    "            new_num = x[:len(x)-i] + \"0\" * i\n",
    "            print(new_num)\n",
    "            return int(new_num, 2)\n",
    "\n",
    "        string = format(n, 'b')\n",
    "        length = len(string)\n",
    "        res = n\n",
    "        for i in range(length):\n",
    "            if string[length-1-i] == '0':\n",
    "                res = res - 2 ** i\n",
    "                continue\n",
    "\n",
    "            if n - 2 ** i < m:\n",
    "                return to_dec(res, i)\n",
    "            res = res - 2 ** i\n",
    "        else:\n",
    "\n",
    "            return to_dec(res, i)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
    "        start = 0\n",
    "        res = n\n",
    "        while n - 2 ** start > 0:\n",
    "            res &= n - 2 ** start\n",
    "            start += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "Solution().rangeBitwiseAnd(2, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_dec(num, i):\n",
    "    x = format(num, 'b')\n",
    "    new_num = x[:len(x)-i-1] + \"0\" * (i+1)\n",
    "    print(new_num)\n",
    "    return int(new_num, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "1100000\n"
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "96"
     },
     "metadata": {},
     "execution_count": 84
    }
   ],
   "source": [
    "to_dec(97, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert Solution().rangeBitwiseAnd(5, 7) ==  4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert Solution().rangeBitwiseAnd(96, 1021) ==  0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert Solution().rangeBitwiseAnd(20, 2000000) ==  0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert Solution().rangeBitwiseAnd(2, 4) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}